/**
 * 2017年3月7日
 */
package algorithm;

/**
 * @author Alex
 *
 */
public class Quick3Way {

	/**
	 * 也就是三色排序
	 * @param args
	 */
	public static void main(String[] args) {
		int arr[] = {'R','B','W','W','R','W','B','R','R','W','B','R'};
		sort(arr,0,arr.length-1);
		for(int i:arr){
			System.out.println((char)i);
		}

	}
	
	public static void sort(int arr[],int lo,int hi){
		if(lo>=hi) return;
		int v = arr[lo];
		int i = lo+1;
		int gt = hi;
		int lt = lo;
		while(i<=gt){
			if(arr[i]>v){
				swap(arr,i,gt--);
			}else if(arr[i]<v){
				swap(arr,i++,lt++);
			}else{
				i++;
			}
		}

		sort(arr,lo,lt-1);
		sort(arr,gt+1,hi);
		
	}
	public static void swap(int arr[],int i,int j){
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

}
